package p300;

import java.util.Arrays;

public class Leetcode_354 {
    public int maxEnvelopes(int[][] envelopes) {
        int len = 0;
        int[] res = new int[envelopes.length];
        Arrays.sort(envelopes, (v1, v2) -> v1[0] == v2[0] ? v2[1] - v1[1] : v1[0] - v2[0]);
        for (int[] envelope : envelopes) {
            int idx = Arrays.binarySearch(res, 0, len, envelope[1]);
            idx = idx < 0 ? -idx - 1 : idx;
            res[idx] = envelope[1];
            if (idx == len) {
                len++;
            }
        }
        return len;
    }

    public static void main(String[] args) {
        Leetcode_354 l = new Leetcode_354();
        System.out.println(l.maxEnvelopes(new int[][]{{4, 5}, {4, 6}, {6, 7}, {2, 3}, {1, 1}}));
    }
}
